/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 * };
 */

class Solution {
  public:
    /* 归并排序 */
    ListNode* Merge(ListNode* left, ListNode* right) {
        ListNode* dummy = new ListNode (-1);  // 排序链表头节点
        ListNode* cur = dummy;

        // merge开始合并
        while (left && right) {
            if (left->val < right->val) {
                cur->next = left;
                left = left->next;
            } else {
                cur->next = right;
                right = right->next;
            }
            cur = cur->next;
        }
        if (left) cur->next = left;
        if (right) cur->next = right;

        return dummy->next;
    }

    ListNode* sortInList(ListNode* head) {
        if (head == NULL || head->next == NULL) return head;
        // 快慢指针找到中点(偶数为前一个)
/* !fast */ 
        ListNode* fast = head, *slow = head;
        while (fast->next != nullptr && fast->next->next != nullptr) {
            fast = fast->next->next;
            slow = slow->next;
        }
        ListNode* mid = slow->next;  // 中点
        slow->next = nullptr;   // 断开链表

        // 递归分解子链表
        ListNode* left = sortInList(head);
        ListNode* right = sortInList(mid);

        return Merge(left, right);
    }
};